package com.my.algorithmlearning.leetcode;

import org.apache.commons.collections4.CollectionUtils;
import org.apache.commons.collections4.ListUtils;
import org.apache.commons.lang3.StringUtils;
import org.springframework.util.Assert;

import java.util.*;

/**
 * @ClassName Medium_17_LetterCombinations
 * @Description Medium_17_LetterCombinations
 * @Author wanghaiwei
 * @Date 2023/2/3 16:12
 */
public class Medium_17_LetterCombinations {
    public List<String> letterCombinationsRecursive(String digits) {
        if (digits == null || digits.length() == 0) {
            return new ArrayList<String>();
        }
        char firstChar = digits.charAt(0);
        String[] firstCharCombination = new String[0];
        if ('2' == firstChar) {
            firstCharCombination = new String[]{"a", "b", "c"};
        }
        if ('3' == firstChar) {
            firstCharCombination = new String[]{"d", "e", "f"};
        }
        if ('4' == firstChar) {
            firstCharCombination = new String[]{"g", "h", "i"};
        }
        if ('5' == firstChar) {
            firstCharCombination = new String[]{"j", "k", "l"};
        }
        if ('6' == firstChar) {
            firstCharCombination = new String[]{"m", "n", "o"};
        }
        if ('7' == firstChar) {
            firstCharCombination = new String[]{"p", "q", "r", "s"};
        }
        if ('8' == firstChar) {
            firstCharCombination = new String[]{"t", "u", "v"};
        }
        if ('9' == firstChar) {
            firstCharCombination = new String[]{"w", "x", "y", "z"};
        }
        if (digits.length() == 1) {
            return new ArrayList<>(Arrays.asList(firstCharCombination));
        }
        List<String> subStrs = letterCombinationsRecursive(digits.substring(1));
        List<String> result = new ArrayList<>();
        for (String subStr : subStrs) {
            for (int i = 0; i < firstCharCombination.length; i++) {
                result.add(firstCharCombination[i] + subStr);
            }
        }
        return result;
    }

    public List<String> letterCombinationsBacktrack(String digits) {
        List<String> combinations = new ArrayList<String>();
        if (digits.length() == 0) {
            return combinations;
        }
        Map<Character, String> phoneMap = new HashMap<Character, String>() {{
            put('2', "abc");
            put('3', "def");
            put('4', "ghi");
            put('5', "jkl");
            put('6', "mno");
            put('7', "pqrs");
            put('8', "tuv");
            put('9', "wxyz");
        }};
        backtrack(combinations, phoneMap, digits, 0, new StringBuffer());
        return combinations;
    }

    public void backtrack(List<String> combinations, Map<Character, String> phoneMap, String digits, int index, StringBuffer combination) {
        if (index == digits.length()) {
            combinations.add(combination.toString());
        } else {
            char digit = digits.charAt(index);
            String letters = phoneMap.get(digit);
            int lettersCount = letters.length();
            for (int i = 0; i < lettersCount; i++) {
                combination.append(letters.charAt(i));
                backtrack(combinations, phoneMap, digits, index + 1, combination);
                combination.deleteCharAt(index);
            }
        }
    }

    public static void main(String[] args) {
        Medium_17_LetterCombinations solution = new Medium_17_LetterCombinations();
        List<String> result = solution.letterCombinationsRecursive("23");
        Assert.isTrue(CollectionUtils.removeAll(new ArrayList<String>(Arrays.asList("ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf")), result).size() == 0
                , "23，计算错误：预期[ad,ae,af,bd,be,bf,cd,ce,cf]，实际：" + StringUtils.join(result, ","));

        result = solution.letterCombinationsBacktrack("23");
        Assert.isTrue(CollectionUtils.removeAll(new ArrayList<String>(Arrays.asList("ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf")), result).size() == 0
                , "23，计算错误：预期[ad,ae,af,bd,be,bf,cd,ce,cf]，实际：" + StringUtils.join(result, ","));
    }
}
